package com.linyaonan.leetcode.sword_to_offer._53_1;

/**
 * 统计一个数字在排序数组中出现的次数。
 *
 *  
 *
 * 示例 1:
 *
 * 输入: nums = [5,7,7,8,8,10], target = 8
 * 输出: 2
 * 示例 2:
 *
 * 输入: nums = [5,7,7,8,8,10], target = 6
 * 输出: 0
 *  
 *
 * 提示：
 *
 * 0 <= nums.length <= 105
 * -109 <= nums[i] <= 109
 * nums 是一个非递减数组
 * -109 <= target <= 109
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
class Solution {

    /**
     * 一个比较简单的思路是通过二分法找到最左相等索引，然后依次向右直到不相等退出
     * @param nums
     * @param target
     * @return
     */
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            if (nums[0] == target) {
                return 1;
            } else {
                return 0;
            }
        }
        int maxLeftIndex = getMaxLeftIndex(nums, target);
        int c = 0;
        if (maxLeftIndex == -1) {
            return 0;
        } else {
            for (int i = maxLeftIndex; i < nums.length; i++) {
                if (nums[i] != target) {
                    return c;
                } else {
                    c++;
                }
            }
        }
        return c;
    }

    /**
     * 该方法中不考虑异常边界情况，未找到则返回-1
     * @param nums
     * @param t
     * @return
     */
    private int getMaxLeftIndex(int[] nums, int t) {
        int l = 0;
        int r = nums.length - 1;
        int result = -1;
        while (l <= r) {
            int m = l + ((r - l) >> 1);
            int tM = nums[m];
            if (tM == t) {
                result = m;
                r = m - 1;
            } else {
                if (tM > t) {
                    r = m - 1;
                } else {
                    l = m + 1;
                }
            }
        }
        return result;
    }
}